package learn.sort.insertion;

import learn.CommUtil;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        //int[] arr = CommUtil.arr(15);
        int[] arr = {9, 8, 7, 6, 5};
        int[] old = Arrays.copyOf(arr, arr.length);
        CommUtil.printArray("原数组", arr);
        process(arr);
        CommUtil.printArray("排序后", arr);
        CommUtil.check(old, arr);
    }

    /**
     * 将第一数看做一个有序序列，把第二个数到最后一个数当成是未排序序列。
     * 从左到右依次扫描未排序序列，将扫描到的每个数插入有序序列
     * @param arr
     */
    public static void process(int[] arr) {
        //1.从下标为1的元素开始选择合适的位置插入
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int temp = arr[i];
            //2.从右向左,找到插入的位置,并把该位置上及右边的数,向右移动一个位置
            while (j > 0 && temp < arr[j-1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            //3.可以插入了
            if (j != i) {
                arr[j] = temp;
            }
        }


    }
}
